Оптимизация поисковых систем посредством использования данных кликабельности

Торстен Иокаим, Корнелльский университет, Факультет информатики, Итака, Нью-Йорк, 14853 США.

Аннотация

В текущей работе представлена методология по автоматической оптимизации качества поиска посредством использования данных кликабельности. Интуитивно, хорошая система информационного поиска должна ранжировать релевантные документы максимально высоко, когда как менее релевантные страницы веб-сайтов должны располагаться ниже. В то время как существуют и более ранние подходы, связанные с обучением функций ранжирования по образцам, они, как правило, требуют обучающего набора данных, сформированного из элементов, имеющих мануальную оценку релевантности, присвоенную специально обученными экспертами. Это обстоятельство делает такие подходы крайне сложными и дорогостоящими в случае их практического применения на поиске. Целью настоящего исследования является разработка методологии, которая использует для обучения данные кликабельности, а именно логи запросов с которыми пользователи обращаются на поиск в связке с логами пользовательских проходов по гиперссылкам, ведущих со страниц результатов алгоритмической выдачи на оригиналы веб-документов. Поиск изобилует подобного рода данными и они могут записываться с минимальными затратами. Используя Машину Опорных Векторов (SVM), текущая работа предлагает алгоритм для обучения функций ранжирования информационного поиска. С теоретической точки зрения, указанный метод демонстрирует свою обоснованность в фреймворке минимизации рисков. Более того, он демонстрирует возможность работы даже с большими наборами запросов и особенностей. Теоретические результаты подтверждаются в ходе контролируемого эксперимента. Он показывает, что указанный алгоритм может эффективно приспосабливать функцию ранжирования метапоисковой машины к определенной группе пользователей, превосходя Google с точки зрения качества поиска только после пары сотен обучающих образцов.

1. Введение

Какую интернет-страницу / страницы в действительности желает получить пользователь, когда обращается на поиск с какими-либо ключевыми фразами, составляющие его вопрос? Как правило, в ответ на его запрос возвращаются тысячи документов, которые хоть и содержат слова из пользовательского вопроса, но его самому оказываются интересны гораздо меньшее их подмножество. Можно просто попросить пользователя сообщить нам необходимую информацию. Если бы мы знали о том наборе интернет-страниц, которые действительно релевантны запросу пользователя, мы бы могли использовать его в качестве обучающего набора для оптимизации (или даже персонализации) функции ранжирования. К сожалению, опыт демонстрирует, что пользователи крайне редко готовы предоставить поиску явную обратную связь. Однако настоящее исследование утверждает, что достаточный объем необходимой нам информации уже сокрыт в лог-файлах систем информационного поиска. Поскольку крупнейшие поисковые машины получают миллионы запросов ежедневно, такого рода данные имеются у них в изобилии. По сравнению с данными явной обратной связи, которые, как правило, выявляются в трудоемких исследованиях пользовательского поведения, любая информация, которая может быть извлечена из лог-файлов практически не сопряжена с финансовыми затратами и в значительной степени более современна.

В настоящей работе представлен подход по обучению функций ранжирования на основе анализа того, на какие ссылки кликает пользователь в представленном ранжировании. Это приводит к задачи обучения с предпочтением, как, например, «по заданному запросу q, документ d_a следует отранжировать выше, нежели чем документ d_b». В более общем смысле, я буду формулировать указанную задачу обучения функции ранжирования по конечной области с точки зрения минимизации эмпирического риска. Для указанной формулировки я представлю алгоритм Машины Опорных Векторов (SVM), который приводит к выпуклому плану (convex program) и может быть расширен до нелинейных функций ранжирования. Эксперименты демонстрируют, что предложенный метод может успешно обучить высокоэффективную функцию ранжирования для метапоисковой машины. Текущая работа организована следующим образом. Она начинается с определения того, что именно понимается под данными кликабельности; каким образом осуществляется запись; как указанные данные могут быть использованы для создания обучающих образцов в форме предпочтений. Далее, Раздел 3 знакомит нас с основным фреймворком для обучения функций ранжирования, приводящего к алгоритму SVM для обучения параметризованного упорядочивания (parameterized orderings) в Разделе 4. В Разделе 5 осуществляется оценка метода на основании экспериментальных результатов.

2. Данные кликабельности в системах информационного поиска

Данные кликабельности в поисковых системах могут быть рассмотрены в качестве триплетов (q, r, c), включающих в себя пользовательский запрос q; результат ранжирования r, предложенный пользователю поиска, и набор c ссылок на оригиналы веб-документов, по которым указанный пользователь совершил переход. Рисунок 1 иллюстрирует указанное рассмотрение на следующем примере: пользователь обратился на поиск с запросом «машина опорных векторов», в ответ на которой система возвратила перечень результатов, который и продемонстрирован на Рисунке 1; затем, пользователь проследовал на оригиналы страниц сайтов, занимающих 1,3 и 7 место в органической выдаче. Поскольку каждому запросу соответствует один триплет, объем потенциально доступных данных практически неограничен. Очевидно, что пользователи не совершают кликов в случайном порядке, и их выбор (в какой-то степени) является осознанным. Вопреки тому обстоятельству, что данные кликабельности, как правило, зашумлены и клики не отражают суждения об «идеальной» релевантности, они, вероятно, все-таки сообщают некоторую информацию. Ключевой вопрос заключается в следующем: каким образом указанная информация может быть извлечена? Однако прежде того, как мы выделим модель того, каким образом могут быть проанализированы данные кликабельности, давайте сперва рассмотрим то, каким же именно образом они могут быть записаны.

2.1 Запись данных кликабельности

Данные кликабельности могут быть записаны с минимальными накладными расходами и без ущерба для функциональности и полезности системы информационного поиска. В частности, по сравнению с пользовательской явной обратной связью, их запись не увеличивает количество накладных расходов для пользователя. Запрос q и возвращенный ответ r может быть без проблем записан при отображении пользователю списка поисковых результатов. Что касается записи кликов, то простая прокси-система может хранить лог-файл. Для экспериментов, которые были проведены в текущей работе, была использована следующая система.

Каждому запросу назначался уникальный ID, который сохранялся в логе запроса вместе со словами, составляющие сам запрос, и представленным результатом ранжирования. Ссылки, представленные в результатах органической выдачи, указывали на оригинал веб-документа не напрямую, а через прокси-сервер. Эти ссылки кодировали ID запроса и URL предложенного пользователю документа. Когда пользователь кликал по одной из указанных ссылок, прокси-сервер записывал в логе кликов как URL-адрес, так и ID запроса. Затем, прокси использует команду HTTP Location для перенаправления пользователя на целевой URL. Для пользователя поиска указанный процесс может быть реализован транспарентно, а для самого поискового механизма без какого-либо отрицательного воздействия на его производительность. Все вышеописанное демонстрирует нам то, что данные кликабельности могут легко записываться с учетом минимальных затрат. Давайте теперь постараемся ответить на ключевой вопрос о том, каким же именно научно-теоретическим и эффективным способом можно проанализировать данные кликабельности.

2.2 Какого рода информацию сообщают данные кликабельности?

Существуют сильные зависимости между всеми тремя частями триплета (q, r, c). Результат ранжирования r, предложенный пользователю в ответ на его запрос q определяется функцией ранжирования, реализованной на поиске. Более того, набор c пройденных пользователем ссылок определяется как самим запросом q, так и предложенным результатом органической выдачи r. Во-первых, пользователь с большей вероятностью проходит по тем ссылкам, которые релевантны его запросу q [16]. Несмотря на то, что указанная зависимость является желательной и интересной для анализа, зависимость кликов от возвращенных пользователю результатах ранжирования r вносит неясность. В частности, пользователь с меньшей вероятностью кликает по ссылкам, которые располагаются ниже в списке возвращенных ответов, вне зависимости от того, релевантны ли они его запросу или нет. В экстремальном случае, вероятность того, что пользователь пройдет по ссылке, которая отображается на 10000 месте практически равна нулю даже в том случае, если рассматриваемый документ наиболее релевантен введенному запросу. Ни один пользователь поиске не станет прокручивать возвращенные ответы настолько, чтобы обнаружить указанный URL. Следовательно, для того, чтобы получить интерпретируемые и значимые результаты из данных кликабельности, необходимо рассмотреть и смоделировать зависимость c от q и r соответствующим образом. Прежде, чем мы опишем подобную модель, давайте сперва рассмотрим интерпретацию данных кликабельности, которые ей не соответствуют. Клик по отдельному URL-адресу не может рассматриваться как абсолютная оценка релевантности. Рассмотрим следующие эмпирические данные, представленные в Таблице 1.

Таблица 1. Средний клик-ранг (clickrank) для трех функций ранжирования («bxx», «tfc» [23] и стратегии «мануальной настройки», при которой используются различные веса в соответствии с HTML-тэгами), реализованных на LASER. Строчки соответствуют методам ранжирования, применяемым на LASER во время исполнения запроса; столбцы содержат значения, вытекающие из последующей оценки метода с прочими алгоритмами. Представленные цифры являются средними рангами кликов и +/- двумя стандартными ошибками. Данные для приведенной таблицы взяты из работы [5].

Данные были взяты из работы [5] и записаны для системы информационного поиска LASER, покрывающей веб-граф Школы информатики Центрального Мичиганского Университета. Таблица демонстрирует средний ранг пользовательских кликов, приходящихся на запрос (например, 3.67 в примере, представленном на Рисунке 1). Каждая ячейка таблицы содержит средний клик-ранг для трех отдельных стратегий поиска информации, усредненных по ~1400 пользовательским запросам. Средний клик-ранг практически равен для всех методологий. Однако, в соответствии с субъективными оценками, все три функции ранжирования существенно отличаются друг от друга в плане предоставляемого ими качества поиска. Наблюдаемое отсутствие разницы между средним клик-рангом может быть разъяснено следующим образом. Поскольку пользователи, как правило, сканируют только первые l ссылок (например, l~10 [24]), возвращенных в ответ на их запрос, прохождение по какой-либо ссылке не может интерпретироваться как оценка релевантности по абсолютной шкале. Возможно, что тот документ, который ранжируется существенно ниже в результатах органической выдачи, мог оказаться более релевантным пользовательскому запросу, однако сам пользователь не увидел его в принципе. Из этого следует, что пользователи совершают переходы по тем ссылкам, которые находятся в ТОП l и кажутся им (относительно) наиболее перспективными в задачах поиска ответа на свой вопрос, вне зависимости от их абсолютной релевантности. Каким образом указанные относительные оценки предпочтений могут быть записаны и проанализированы?

Давайте снова вернемся к нашему примеру, изображенному на Рисунке 1. Несмотря на то, что мы не можем сделать вывод о том, что ссылки 1,3 и 7 релевантны по абсолютной шкале, куда более правдоподобным представляется вывод о том, что ссылка 3 более релевантна, чем ссылка 2 с вероятностью выше, нежели чем случайный клик. Полагая, что заданный пользователь просканировал возвращенный перечень поисковых результатов от начала до самого конца, он должен был обнаружить 2 ссылку до того, как прошел по 3 URL-адресу, принимая решение об игнорировании второго ответа поисковой системы. Допуская, что составленные для всех ссылок сниппеты являются достаточно информативными, подобного рода предположение позволяет получить некоторое представление о предпочтениях пользователя. Аналогично, вероятней всего, ссылка 7 субъективно представляется пользователю более релевантной, нежели чем ссылки 2, 4, 5 и 6. Это означает, что данные кликабельности не сообщают нам абсолютные оценки релевантности, а лишь неполные относительные оценки релевантности по просмотренным пользователем. Система информационного поиска, ранжирующая возвращенные ссылки на оригиналы веб-документов в соответствии с их релевантностью относительно запроса q, должна отранжировать ссылку 3 выше, чем 2, а ссылку 7 поместить до 2, 4, 5 и 6 ссылки. Указывая предпочтенный пользователем результат ранжирования с r*, мы получаем неполную (и потенциально зашумленную) информацию вида:

Описанную стратегию по извлечению предпочтительной обратной связи (preference feedback) можно представить в виде следующего алгоритма:

Алгоритм 1 (извлечения предпочтительной обратной связи из данных кликабельности).

К сожалению, указанный тип обратной связи не подходит для стандартных алгоритмов машинного обучения. Далее вводится новый алгоритм обучения, такой, что этот «слабый» тип относительной обратной связи может применяться в качестве обучающего набора.

3. Фреймворк для обучения функций поиска

Задача информационного поиска может быть формализована следующим образом. Для заданного запроса q и коллекции документов D = {d₁, …, d_m}, оптимальная поисковая система должна возвратить результат ранжирования r*, который упорядочит указанные документы в коллекции D в соответствии с их релевантностью пользовательскому запросу. Несмотря на то, что запрос, чаще всего, представляет собой не более чем набор ключевых слов, на более абстрактном уровне он также может содержать информацию о пользователе и состоянии информационного поиска. Как правило, поисковые системы не могут достичь оптимального упорядочивания r*. Вместо этого, оперативная функция поиска f оценивается тем, насколько сильно ее упорядочивание r_f(q) аппроксимирует к оптимальному. Говоря более формально, как r*, так и r_f(q) являются бинарными отношениями по DxD, которые выполняют особенности слабого ранжирования, то есть r* ⊂ DxD и r_f(q) ⊂ DxD, будучи асимметричными и отрицательно-транзитивными. В том случае, если документ d_i отранжирован выше, чем d_j в упорядоченном рейтинге результатов r, то есть d_i <r d_j, тогда (d_i, d_j) ∈ r, в противном случае (d_i, d_j) ∉ r. Если не оговорено иное, давайте для простоты предположим, что как r*, так и r_f(q) строго упорядочены. Это означает, что для всех пар (d₁, d₂) ∈ DxD либо d_i <r d_j или d_j <r d_i. Однако несложно обобщить большинство следующих результатов к r* при слабой упорядоченности. Какая же мера сходства между системным r_f(q) и целевым рейтингом r* представляется здесь уместной? Для бинарной шкалы релевантности, Средняя Точность [1] является наиболее частоиспользуемым показателем в информационном поиске. Тем не менее, большинство исследователей, занимающихся вопросами информационного поиска, соглашаются в том, что бинарная релевантность крайне груба, и она используется в качестве упрощающего допущения. Поскольку представленные далее методологии не требуют подобного упрощения, мы отойдем от схемы, использующей бинарную релевантность, и используем τ-Кендалла [19, 21] в качестве критерия качества. В статистических задачах сравнения ранговой корреляции двух случайных величин τ-Кендалла является наиболее частоиспользуемым показателем. Для двух конечно строгих рангов r_a ⊂ DxD и r_b ⊂ DxD, τ-Кендалла может быть определен на основании числа согласующихся пар P  и числа несогласующихся пар (инверсий) Q. Пара d_i ≠ d_j согласуется в том случае, если как r_a, так и r_b сходятся в том, как они упорядочивают d_i и d_j. Несогласованность наблюдается в том случае, если они не согласуются. Отметим, что на конечной области D с m-документов, суммой P и Q является (m / 2) для строгих рангов. В этом случае, τ-Кендалла может быть опредлен как:

В качестве наглядного примера, давайте рассмотрим два результата ранжирования r_a и r_b следующим образом:

Число несогласующихся пар 3 (то есть, {d₂, d₃}, {d₁, d₂}, {d₁, d₃}), в то время, как все оставшиеся 7 пар согласуются. Следовательно,  τ(r_a, r_b) = 0.4. Почему именно эта мера схожести пригодна для информационного поиска? Уравнение (2) зависит только от Q при фиксированной коллекции документов. Принятая в качестве меры расстояния, Q удовлетворяет аксиомам Kemeny и Snell [18] для строгих рангов. Более того, она пропорциональна мере Yao [26], предложенной для оценки систем информационного поиска. В случае применения к бинарной шкале релевантности легко обнаружить, что максимизирование (2) эквивалентно минимизированию среднего ранга релевантных документов. И, наконец, τ(r_f(q), r*) связана со Средней Точностью [1]. В частности, число инверсий Q дает нижнюю границу Средней Точности следующим образом:

R — количество релевантных документов. Доказательство приведено в Приложении. Данные аргументы показывают то, каким образом τ(r_f(q), r*) связана с качеством поиска. Они демонстрируют, что максимизирование τ(r_f(q), r*) связана с улучшением качества поиска во множественных фреймворках. На данном этапе мы в состоянии определить задачу обучения функции ранжирования. Для фиксированного, но неизвестного распределения Pr(q, r*) запросов и целевых рейтингов по коллекции документов D с m-документами, целью является обучение функции ранжирования f(q) для которой ожидаемое τ-Кендалла

максимальна. Обращаем ваше внимание, что (6) пропорционально риску, имеющему функциональную зависимость [25] с -τ в качестве функции потерь. По мере того, как мы определили цель обучения, по прежнему остается открытым вопрос о том, возможна ли разработка алгоритмов машинного обучения, позволяющих оптимизировать (6)?

4. Алгоритм SVM в задачах обучения функции ранжирования

Большинство работ, связанных с машинным обучением в информационном поиске не рассматривают приведенную выше формулировку, а упрощают задачу до проблемы бинарной классификации с двумя классами «релевантный» и «нерелевантный». Подобного рода упрощение имеет ряд недостатков. Например, вследствие значительного преобладания «нерелевантных» документов, ученик, как правило, достигает максимальной аккуратности в предсказании классов, в том случае, если он всегда дает ответ «нерелевантный», вне зависимости от того, где именно ранжируется релевантный документ. Но что более важно, в подразделе 2.2 было продемонстрировано, что подобные абсолютные оценки релевантности не могут извлекаться из данных кликабельности постольку, поскольку они отсутствуют там в принципе. Следовательно, следующий алгоритм непосредственно решает (6), используя подход по минимизации эмпирического риска [25]. Учтивая независимость и одинаковую распределённость образцов в обучающей выборке S размера n, содержащей запросы q с их целевыми рейтингами r*.

ученик L выбирает функцию ранжирования f из семейства ранжирующих функций F, что максимизируют эмпирический риск τ:

на обучающей выборке. Заметим, что указанная схема аналогична, например, классификации посредством минимизации ошибки обучения, за тем исключением, что целью является не отметка класса, а бинарное отношение упорядочения.

4.1 Алгоритм Ranking SVM

Возможна ли разработка таких алгоритмов и семейства ранжирующих функций F, чтобы (а) нахождение функции f ∈ F максимизирующих (8) было эффективным, и (б) чтобы эта функция обобщалась за пределами обучающего набора? Рассмотрим класс линейных функций ранжирования:

где w^→ — это взвешенный вектор, регулируемый обучением; (q,d) представляют собой отображение на характеристики, описывающие соответствие между запросом q и документом d подобно описательно-ориентированному подходу на поиске, предложенного Fuhr и др. [10, 11]. Такие характеристики, как, например, количество слов, пересекающихся в пользовательском запросе и цифровом документе; количество слов, которые пересекаются с ними внутри основных HTML-тэгов (например, TITLE, H1, H2,…) или PageRank документа d [22] (см. также подраздел 5.2).

Рисунок 2 иллюстрирует то, как взвешенный вектор w^→ определяет порядок четырех точек на двухмерном изображении. Для любого взвешенного вектора w^→, точки ранжируются по их проекции на w^→ (или, что эквивалентно, по их отмеченному расстоянию к гиперплоскости с нормальным вектором w^→). Это значит, что для w^→₁ точки отранжируются (1, 2, 3, 4), в то время как w^→₂ означает упорядочивание (2, 3, 1, 4). Вместо непосредственной максимизации (8), это эквивалентно минимизации числа Q несогласующихся пар в Уравнении (2). Для класса линейных функций ранжирования (9), это эквивалентно нахождению взвешенного вектора таким образом, что выполняется максимальное число следующих неравенств:

К сожалению, непосредственное обобщение полученных результатов в работе [13] показало, что указанная задача относится к классу NP-сложных. Однако, аналогично SVM-классификации в [7], мы можем аппроксимировать решение посредством введения (неотрицательных) вспомогательных переменных ξ_i,j,k и минимизации верхней границы Σξ_i,j,k. Добавление SVM регуляризации для максимизации отступа к объекту приводит к следующей задаче оптимизации, схожей с алгоритмом порядковой регрессии из работы [12].

Первая задача оптимизации (Ranking SVM).

C является параметром, позволяющим достигнуть компромисса между размером отступа и ошибкой на обучении. Геометрически, отступом δ является расстояние между двумя ближайшими проекциями внутри всех целевых рейтингов. Это проиллюстрировано на Рисунке 2. Первая задача оптимизации является выпуклой и не имеет локальных оптимумов. При перестановки ограничений (13):

становится очевидным, что указанная задача оптимизации эквивалентна SVM классификации на попарной разности векторов Ф(q_k, d_i) — Ф(q_k, d_j). Вследствие данного сходства, задача может быть решена посредством использования алгоритмов декомпозиции, подобных тем, что применяются в SVM классификации. В дальнейшем, для обучения использовался вариант алгоритма SVM^light [14]. Можно показать, что обучение функции поиска f_w→* всегда может представляться в качестве линейной комбинации векторов особенностей.

Это позволяет использовать Ядра [4, 25] и расширить алгоритм Ranking SVM до нелинейной функции поиска. α*_k,l может быть получена из значений двойственных переменных. Наиболее часто, f_w→* будет использоваться для ранжирования набора документов в соответствии с новым запросом q. В данном случае, этого достаточно для сортировки документов по их значению

Если мы не используем Ядра, указанное свойство делает применение обученной функции поиска крайне эффективным. Существуют быстрые алгоритмы, которые рассчитывают рейтинг на основании линейных функции с помощью инвертированных индексов (например, см. [1]).

4.2 Использование неполной обратной связи

В том случае, если в качестве источника обучающего набора выступают логи кликабельности, полный целевой рейтинг r* по запросу q не наблюдается. Однако, как было показано в подразделе 2.2, подмножество r’ ⊆ r* можно вывести из лог-файла. Достаточно просто адаптировать Ranking SVM к варианту использования подобного рода неполных данных, заменив r* с наблюдаемым предпочтением r’. Учитывая обучающий набор S

с неполной информацией о целевом рейтинге, мы приходим к следующему алгоритму.

Вторая задача оптимизации (Ranking SVM (неполный)).

Итоговая функция поиска определяется аналогично. Используем полученные с помощью этого алгоритма результаты по нахождению функции ранжирования, которая имеет меньшее число несогласующихся пар по отношению к наблюдаемым частям целевого рейтинга.

5. Эксперименты

Проведенные далее эксперименты помогут нам проверить, была ли оправдана цепочка умозаключений, которую мы вывели из данных кликабельности, а также то, способен ли алгоритм Ranking SVM успешно использовать подобную неполную информацию о пользовательских предпочтениях. Для начала мы опишем экспериментальную установку в фреймворке метапоисковой системы. Далее последуют результаты, полученного в ходе оффлайнового и онлайнового эксперимента. Эксперимент, выполненный в режиме оффлайн, имеет своей задачей проверку способности методологии Ranking SVM обучить функцию поиска, максимизируя τ-Кендалла по неполной обратной связи пользовательских предпочтений. Эксперимент, проведенный в режиме онлайн, идет дальше и верифицирует улучшение качества поиска посредством обучения функции ранжирования, то есть именно то, что нам бы хотелось достичь.

5.1 Экспериментальная установка: метапоиск

Для того чтобы извлечь данные и обеспечить фреймворк для тестирования нашего алгоритма, я реализовал метапоисковую систему под названием «Striver». Метапоисковые машины комбинируют и переранжируют результаты нескольких основных систем информационного поиска, не располагая собственной базой данных и поисковым индексом. Подобного рода установка имеет несколько преимуществ. Во-первых, она легкореализуема в задачах покрытия большой коллекции документов, а именно всей Глобальной паутины. Во-вторых, базовые (классические) системы информационного поиска обеспечивают основу для сравнения. Метапоисковая машина Striver работает следующим образом. Пользователь обращается со своим вопросом к интерфейсу Striver. Указанный запрос передается на «Google», «MSNSearch», «Excite», «Altavista» и «Hotbot». Страницы с результатами поиска, возвращаемые этими базовыми поисковыми системами подвергались анализу; извлекался ТОП 100 предложенных ссылок. После канонизации URL-адресов, объединение этих ссылок формировали набор кандидатов V. Метапоисковая машина Striver ранжировала ссылки в V в соответствии с обученной функцией поиска f_w→* и предлагала ТОП50 ссылок нашему пользователю в качестве ответа. Для каждой ссылки машина отображала TITLE страницы вместе с ее URL-адресом. Клики пользователей записывались с использованием системы прокси, описанной нами ранее в подразделе 2.1. Для того, чтобы мы имели возможность сравнить качество различных функций ранжирования, использовалась методология, которая была описана в работе [16]. Ключевой идеей являлось одновременное предложение двух рейтингов. Указанная специальная форма представления приводила к слепой статистической проверке, чтобы пользовательские клики смогли продемонстрировать непредвзятые предпочтения к тому или иному результату. В частности, при сравнении двух результатов органической выдачи А и B, они комбинировались с единый рейтинг C таким образом, чтобы выполнялось следующее условие для любого ТОП l ссылок комбинированного ранжирования. ТОП l ссылок комбинированного рейтинга C содержал ТОП k_a ссылок из А и ТОП k_b ссылок из B, с |k_a-k_b|≤1. Другими словами, если пользователь сканировал ссылки C от самых первых результатов до последних, то он мог увидеть практически одинаковое количество ссылок, как взятое из ТОП А, так и из ТОП B. Как продемонстрировано в [16], подобного рода комбинированное ранжирование существует всегда и может быть реализовано достаточно эффективно. Пример приведен на Рисунке 3.

Результаты двух функций ранжирования скомбинированы в единый рейтинг, который предложен пользователю. Обратите внимание, что сниппеты и все прочие аспекты представления унифицированы таким образом, что пользователь не может сказать, какая же именно стратегия предложила конкретную страницу в качестве ответа. Например, пользователь проходит по 1,3 и 7 ссылке. Какой вывод мы можем сделать исходя из этих кликов? В данном примере пользователь должен был увидеть ТОП4 ссылок из обоих отдельных рейтингов постольку, поскольку он прошел по 7-ой ссылке в комбинированном перечне результатов. Он принял решение пройти по 3 ссылкам, расположенных в ТОП4 рейтинга A (а именно 1,2 и 4), однако только по 1 ссылке из рейтинга B (а именно 1). Разумно сделать вывод о том, что (с вероятностью выше, нежели чем случайный выбор) ТОП4 ссылок из А оцениваются лучше, чем аналогичный ТОП из В по данному запросу. На основании подобного комбинированного ранжирования достаточно несложно разработать механизм проверки гипотез, относительно пользовательских предпочтений. Грубо говоря, в том случае, если пользователь не выражает каких-либо явных предпочтений к результатам ранжирования А или B, он будет одинаково часто совершать переходы по ТОПk ссылок от каждого рейтинга. Если для выборки пар (A₁,B₁), …, (A_s,B_s) пользователь по большей части кликает по тем ресурсам, которые предложены А, чем по B, тогда, следовательно, рейтинг А должен содержать в себе более релевантные ссылки, чем B. Формализуем предположение о том, что:

• пользователь кликает с некоторой ε>0 более часто по более релевантным ссылкам, чем по менее релевантным.
• и решение пользователя о прохождении по какому-либо результату не зависит от прочих факторов (например, ссылки обоих рейтингов А и В выглядят схожим образом)

Те результаты, которые мы получаем с использованием данного метода приводят к схожим результатам оценки с использованием явных асессорских суждений о релевантности для больших S из работы [16].

5.2 Эксперимент, проведенный в режиме оффлайн

Текущий эксперимент верифицирует, что алгоритм Ranking SVM действительно может обучиться закономерностям, используя неполную обратную связь из данных кликабельности. Для генерации первого обучающего набора я использовал поисковую машину Striver по всем моим собственным запросам в течение октября 2001 года. Striver отображал результаты классических поисковых систем Google и MSNSearch, используя комбинированный подход, который был описан в предшествующем разделе. Были записаны все триплеты кликабельности. Это привело к 112 запросам с непустым множеством кликов. Указанные данные обеспечили основу для последующего оффлайнового эксперимента. В целях обучения функции поиска посредством использования алгоритма Ranking SVM необходимо разработать надлежащее отображение признаков Ф(q,d), описывающих соответствие между запросом q и документом d. В нашем эксперименте использовались следующие особенности. Хотя этот набор характеристик, вероятней всего, далек от оптимального набора. Несмотря на то, что многие атрибуты отражают мою интуицию о том, что может иметь значение для обучения качественного поиска, я включил сюда только те характеристики, которые легкореализуемы. Более того, я не осуществлял какого-либо отбора особенностей или подобного рода настройки. Были реализованные следующие особенности:

• Ранг в других системах информационного поиска (всего 38 особенностей):
  • rank_X: 100 минус ранг в X ∈ {Google, MSN-Search, Altavista, Hotbot, Excite} деленный на 100 (минимум 0)
  • top1_X: занимающий место #1 в X ∈ {Google, MSN-Search, Altavista, Hotbot, Excite} (бинарно {0, 1})
  • top10_X: попавший в ТОП10 в X ∈ {Google, MSN-Search, Altavista, Hotbot, Excite} (бинарно {0, 1})
  • top50_X: попавший в ТОП50 в X ∈ {Google, MSN-Search, Altavista, Hotbot, Excite} (бинарно {0, 1})
  • top1count_X: занимающий место #1 в X из 5 поисковых систем
  • top10count_X: попавший в ТОП10 в X из 5 поисковых систем
  • top50count_X: попавший в ТОП50 в X из 5 поисковых систем
• Соответствие запроса/содержимого (всего 3 особенности):
  • query_url_cosine: пересечение слов, составляющих запрос и URL-адрес (диапазон [0,1])
  • query_abstract_cosine: пересечение слов, составляющих запрос и TITLE (диапазон [0,1])
  • domain_name_in_query: пользовательский запрос содержит доменное имя (бинарно {0,1})
• Популярные атрибуты (всего 20.000 особенностей):
  • url_length: длина URL-адреса в символах, разделенная на 30
  • country_X: код страны X URL-адреса (бинарный атрибут {0,1} для каждого кода страны)
  • domain_X: домен X URL-адреса (бинарный атрибут {0,1} для каждого доменного имени)
  • abstract_contains_home: слово «главная», появляющаяся в URL-адресе или TITLE документа (бинарный атрибут {0,1})
  • url_contains_tilde: URL-адрес содержит «~» (бинарный атрибут {0,1})
  • url_X:URL-адрес X в качестве неделимого объекта (бинарный атрибут {0,1})

Из указанных 112 запросов в соответствии с Алгоритмом 1, который был описан в подразделе 2.2, были извлечены попарные предпочтения. Кроме того, было добавлено 50 ограничений для каждого документа, по которому был совершен переход, указывающих на то, что он должен ранжироваться выше, нежели какой-либо случайный документ наборе кандидатов V. Несмотря на то, что последние ограничения не были основаны на пользовательской обратной связи, в большинстве случаев они должны сохраняться по отношению к оптимальному ранжированию. Эти дополнительные ограничения помогут стабилизировать результаты обучения и сохранить обученную функцию ранжирования несколько ближе к оригинальному поиску. Рисунок 4 демонстрирует предсказательную эффективность алгоритма Ranking SVM.

Для создания графика полный набор данных разбивался случайным образом на обучающее и проверочное множество. Ось абсцисс демонстрирует количество запросов, использованных для обучения. Ось ординат демонстрирует процент попарных ограничений предпочтений, не исполненных на проверочном наборе. Каждая точка является усредненным значением по 10 (5-20 обучающих запросов) / 20 (40-80 обучающих запросов) различных тестовых/обучающих разбиений. При обучении алгоритма Ranking SVM не используется ядро и C, компромисс между ошибкой на обучении и отступом (margin) был выбран из C ∈ {0.001, 0.003, 0.005, 0.01} посредством минимизации исключения по одной ошибки на обучающем наборе. График демонстрирует, что Ranking SVM способен обучаться закономерностям на предпочтениях. Ошибка тестирования уменьшается примерно до 10%. График также показывает количество ограничений, нарушенных результатами выдачи Google и MSNSearch. Доля их ошибок существенно больше, нежели чем обученной функции поиска. Это результаты дают первое доказательство концепции и оправдывают проведенный крупномасштабный эксперимент с многочисленными пользователями. В частности, по мере того, как оффлайновый эксперимент верифицирует, что алгоритм Ranking SVM способен научиться предсказывать предпочтительные ограничения, до сих пор нерешенным остается вопрос о том, возможно ли улучшение качества поиска посредством обучения функции ранжирования с объективной точки зрения. Ответ на этот вопрос дается в нашем следующем эксперименте.

5.3 Интерактивный эксперимент, проведенный в режиме онлайн

Для того чтобы продемонстрировать, что обученная функция ранжирования улучшает информационный поиск, был проведен следующий эксперимент. Начиная с 31 октября 2001 года, мы предложили Striver группе пользователей, состоящий из примерно 20 человек. Группа включала в себя исследователя и студентов подразделения ИИ Дортмундского университета, под руководством профессора К. Морика. Им было предложено использовать поиск Striver точно также, как если бы они искали ответ на свой вопрос в любой другой классической поисковой системе. К 20 ноября 2001 года, машина собрала 260 обучающих запросов (имеющих по крайней мере 1 клик по возвращенным результатам). Ranking SVM был обучен по этим запросам, используя схожее Ф(q, d) и схожую общую установку, что было описано ранее. Затем обученная функция была реализована на поиске Striver и использована в задачах ранжирования набора кандидатов V. В течение оценочного периода, продолжавшегося до 2 декабря 2001 года, обученный поиск сравнивался с:

• Google
• MSNSearch
• TopRank: базисная метапоисковая машина, которая ранжирует ссылки, возвращенные на первую позицию либо Google, MSNSearch, Altavista, Excite или Hotbot, до второй ссылки; до третьей ссылки и т. д.

Различные стратегии сравнивались с использованием методологии, описанной в подразделе 5.1. Стратегия обученного поиска была представлена в комбинации с одним из трех базисных рейтингов, избранных случайным образом. Таблица 2 демонстрирует то, по какому множеству запросов пользователи кликали по большему/меньшему числу ссылок, составляющих ТОП обученной функции ранжирования. В первой строчке таблицы обученный поиск сравнивается с Google. По 29 запросам пользователи больше проходили по тем ссылкам, которые возвращались обученной функцией; по 13 запросам они больше кликали по ссылкам, предложенным классической поисковой системой Google; и, наконец, по 27+19 запросов, кликов было осуществлено в равном количестве (или они отсутствовали). При использовании двухстороннего биномиального критерия знаков, разница достигла существенного уровня в 95%, приведя к заключению о том, что для данной группы пользователей обученная функция поиска эффективней, нежели чем Google. То же самое относится и к двум другим сравнениям.

5.4 Анализ обученной функции

Предыдущий результат показывает, что обученная функция улучшает качество поиска. Поскольку Ranking SVM обучает линейную функцию, мы можем проанализировать функцию посредством изучения обученных весов. Таблица 3 отражает веса некоторых особенностей, в частности те, что имеют самые высокие абсолютные веса. Грубо говоря, высокий положительный (отрицательный) вес указывает на то, что документы с указанными особенностями должны ранжироваться выше (ниже) в результатах алгоритмической выдачи. Веса, представленные в Таблице 3, обоснованны для этой группы пользователей. Поскольку множество вопросов требовало возврата научного материала, выглядит вполне естественным то, что URL-адреса, ассоциированные с доменом «citeseer» (и алиасом «nec») получили положительный вес. Весами, которые имеют наибольшее значение, являются те, что относятся к пересечению слов, составляющих запрос и сниппет; наличием URL в ТОП 10 поисковой системы Google; к пересечению термов, составляющих запрос и URL-адрес. Документ получает большой отрицательный вес в том случае, если не находится в ТОП1 какой-либо поисковой системы; не находится в ТОП 10 какой-либо поисковой системы (обратите внимание, что второе подразумевает первое); в том случае, если URL-адрес длинный. Все указанные веса имеют свое обоснование и интуитивный смысл.

6. Обсуждение и смежные работы

Экспериментальные результаты продемонстрировали, что алгоритм Ranking SVM может успешно обучать улучшенную функцию поиска посредством использования данных кликабельности. Без какой-либо явной обратной связи или мануальной настройки параметров, он автоматически адаптировался к специфическим предпочтениям группы, состоящий из ~ 20 пользователей. Это усовершенствование свидетельствует не только о верификации того, что Ranking SVM может обучаться с помощью неполной обратной связи, следующей из результатов ранжирования, но также является весомым аргументом в пользу персонализации функций поиска. В отличе от традиционных поисковых систем, которые должны «аппроксимировать» свою функцию ранжирования к крупным и, следовательно, разнородным группам пользователей по причине затрат, связанных с мануальной настройкой, технологии машинного обучения могут существенно улучшить качество поиска, посредством адаптирования функции ранжирования к малым и однородным группам (или, даже, персонализации) без непомерно высоких издержек.

В то время как в научной сфере существуют более ранние исследования, посвященные обучению функций поиска (например, [10]), большинство методологий требуют явной оценки релевантности. Наиболее тесно-связанным является подход, предложенный Bartell и др. [2]. Они предложили модели коллектива экспертов (mixture-of-experts algorithms) для линейной комбинации экспертного ранжирования посредством максимизации отличного критерия ранговой корреляции. Однако они полагаются на явные суждения о релевантности. Схожий алгоритм, комбинирующий рейтинги, был предложен Cohen и др. [6]. Они показали как эмпирически, так и теоретически, что их алгоритм обнаруживает такую комбинацию, которая исполняется наиболее близко к лучшему из основных экспертов. Алгоритм бустинга Freund и др. [9] представляет собой подход, объединяющий множество слабых ранжирующих правил в сильную функцию ранжирования. Несмотря на то, что они также (аппроксимировано) минимизировали количество инверсий, они явно не рассматривали распределение по запросам и целевым результатам ранжирования. Однако именно их алгоритм, вероятней всего, может быть адаптирован к настройке, рассмотренной в текущей работе. Наиболее тесно-связанным алгоритмически является SVM-подход к порядковой регрессии, предложенный Herbrich и др. в работе [12]. Но, опять же, они рассматривают отличную модель выборки. В порядковой регрессии все объекты взаимодействуют и ранжируются по схожей шкале. В задаче ранжирования данных в информационном поиске результаты органической выдачи должны согласовываться только внутри какого-либо запроса, но никак не между запросами. Это делает задачу ранжирования менее связанной. Например, задача ранжирования двух документов d_i и d_j может в конечном счете привести к существенно различным результатам поиска по двум различным запросам q_k и q_l даже в том случае, если они имеют точно такой же вектор особенностей (то есть, Ф(q_k, d_i) = Ф(q_l, d_j)). Простой, персептроно-подобный алгоритм для порядковой регрессии был относительно недавно предложен Crammer и Singer [8]. Интересен вопрос о том, может ли подобного рода онлайновый алгоритм также использоваться в решении задачи оптимизации, взаимодействуя с Ranking SVM. Были предприняты некоторые попытки по использованию неявной обратной связи посредством наблюдения за поведением кликов в системах информационного поиска [5] и браузерных приложений [17, 20]. Тем не менее, семантика процесса обучения и его результаты до конца неясны, как было продемонстрировано в подразделе 2.2. Коммерческая поисковая система «Direct Hit» использует данные кликабельности. Механизм работы которой, однако, не опубликован. В работе [3] было предложено интересное использование данных кликабельности для решение другой задачи. Здесь авторы использовали данные кликабельности для идентификации релевантных запросов и URL-адресов.

Каковы вычислительные требования обучения Ranking SVM по данным кликабельности? Поскольку SVM^light [15] решает двойственную задачу оптимизации, они зависят только от внутренних произведений между векторами особенностей Ф(q,d). В том случае, если эти векторы особенностей разреженны, как указывалось выше, SVM^light может эффективно обработать миллионы особенностей. Самое большое влияние на время обучения оказывает количество ограничений во второй задаче оптимизации. Однако, в случае использования данных кликабельности, число ограничений масштабируется исключительно линейно с количеством запросов, если число кликов приходящихся на запрос имеет верхнюю границу. В других приложениях алгоритм SVM^light уже продемонстрировал возможность решения задач с несколькими миллионами ограничений, посредством использования обычного настольного компьютера. Тем не менее, масштабирование в порядке обнаруженного размера остается интересной и открытой проблемой поиска.

7. Заключения и будущая работа

В текущей работе был представлен подход по майнингу лог-файлов систем информационного поиска с целью автоматического улучшения производительности их поиска. Ключевым моментом настоящего исследования является то, что подобного рода данные кликабельности могут обеспечить обучающий набор необходимой информацией в форме относительных предпочтений. Опираясь на новую формулировку задачи обучения в информационно поиске, это исследование выводит алгоритм для обучения функции ранжирования. Используя метод опорных векторов, итоговая задача обучения оказывается разрешимой даже на большим количестве запросов и большом числе особенностей. Результаты экспериментов демонстрируют, что алгоритм хорошо работает в практических условиях, успешно адаптируя функцию поиска метапоисковой машины к предпочтениям группы пользователей. Настоящая работа порождает целую серию вопросов, затрагивающих использование машинного обучения на системах информационного поиска. Какой размер группы пользователей является оптимальным и каким образом подобного рода группы могут быть определены? Очевидно, существует компромисс между объемом обучающего набора (то есть, величиной группы) и максимальной однородностью (то есть, единичный пользователь). Возможно ли использовать алгоритмы кластеризации в задачах обнаружения однородных групп пользователей? Более того, могут ли данные кликабельности также использоваться для адаптации поиске не к группе пользователей, а к особенностям определенной коллекции документов? В частности, настройки разработчиков любой из существующих поисковых систем обязательно субоптимальны для любой конкретной коллекции. Однако наш алгоритм не ограничивается метапоисковой машиной. Существует множество ситуаций, при которых целью обучения является построение ранга на основании некоторых параметров (например, запроса). В частности, большинство рекомендательных задач может быть решено подобным способом. Особенно интересным в рекомендательных установках является тот факт, что алгоритм Ranking SVM может быть обучен с неполными данными о предпочтениях. Например, рассмотрим рекомендательную систему, целью которой является обучение на моих телевизионных предпочтениях. Наблюдая за моим поведением, складывающимся в ходе «телевизионного серфинга», система может сделать выводы о том, какие же именно программы я предпочитаю смотреть по сравнению с другими в какое-либо определенное время. Но, опять же, это относительное предпочтение, а не предпочтение по абсолютной шкале. Открытым вопросом, который касается самого алгоритма, является его теоретическое описание и эффективность реализации. Возможно ли доказать обобщение границ на основании отступа? Или, еще интересней с практической точки зрения, возможно ли проанализировать процесс множественных шагов по обучению/получению обратной связи в смысле инкрементального онлайнового алгоритма? Как было подробно рассмотрено ранее, существует зависимость между ссылками, предложенными пользователю, и теми, по которым система получила обратную связь. Было бы интересно заняться изучением свежих идей, связанных с обучением, для оптимизации этой обратной связи. В этом фреймворке также возможно исследовать механизмы, позволяющие увеличивать сопротивляемость алгоритмов к продвижению сайтов. На текущем этапе пока не ясно то, каким образом единичный пользователь поиска может повлиять на функцию ранжирования, посредством неоднократного прохождения по избранным ссылкам. Рассматривая алгоритмы, предназначенные для решения задачи оптимизации, мы приходим к выводу, что, вполне вероятно, их быстродействие в перспективе может быть ускорено по той простой причине, что ограничения имеют специальную форму. В частности, онлайновые алгоритмы могут оказаться более подходящими для настройки многих приложений.

8. Благодарности

Большое спасибо профессору Морику и подразделению ИИ Дортмундского университета за оказанную ими помощь и предоставленные ресурсы для проведения экспериментов. Также выносится благодарность Ричу Каруана, Александру Никулеску-Мизилу, Фиби Сенгерс, Джону Клейнбергу и Лилиан Ли за полезные обсуждения, а также Виму Верхагу за оказанную консультацию по рекомендательным системам.

Приложение

Теорема 1. Пусть r_rel является результатом ранжирования, размещающим все релевантные документы выше всех нерелевантных документов и пусть r_sys является обученным поиском. Если Q — это число несогласующихся пар между r_rel и r_sys, тогда средняя точность составляет по крайней мере

если имеются R релевантных документов.

Доказательство. Если p₁, …, p_R ранги релевантных документов в r_sys, отсортированных в порядке возрастания, тогда Средняя Точность может быть рассчитана как:

Каково минимальное значение AvgPrec(r_sys, r_rel), учитывая, что количество несогласующихся пар фиксировано? Легко увидеть, что сумма рангов p₁ + … + p_R связана с количеством несогласующихся пар Q следующим образом:

На текущем этапе возможно указать нижнюю границу в виде следующей целочисленной задачи оптимизации. Она рассчитывает наихудшую Среднюю Точность для фиксированного значения Q.

Упрощение задачи путем удаления двух последних наборов ограничений может только уменьшить минимум таким образом, что решение без ограничений по-прежнему будет ниже границы. Оставшаяся задача является выпуклой и может быть решена с использованием множителей Лагранжа. Лангранжианом является

На минимуме задачи оптимизации, Лангранжиан, как известно, имеет частные производные равные нулю. Начинаем с частных производных для p_i

решая для p_i, и подставляя обратно в Лангранжиан, мы приходим к:

Теперь возьмем производную по отношению к β

решая для β, и снова подставляя в Лагранджиан, мы приходим к требуемому решению.